import java.util.*;


public class Solution10 {
    public static void main(String[] args) {
        Solution10 solution10 =new Solution10();
        List<List<String>> lists = solution10.solveNQueens(4);
        System.out.println(lists);
    }
    private List<List<String>> result = new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        //Q所能攻击的范围为米字型，采用回溯的方法进行试探
        Set<Integer> columns = new HashSet<>();//存储不同层的皇后所在的列
        Set<Integer> pie = new HashSet<>();
        Set<Integer> na = new HashSet<>();
        List<String> list = new ArrayList<>();
        _findQueens(0,n,columns,pie,na,list);
        //输出一个list
        return result;
    }
    private void _findQueens(int level,int n,Set<Integer> columns,Set<Integer> pie,Set<Integer> na,List<String> list){
        if(level == n) {
            result.add(new ArrayList<>(list));
            return;
        }
        for(int i = 0;i<n;i++){
            StringBuilder sb = new StringBuilder();
            if(columns.contains(i) || pie.contains(level+i) || na.contains(i-level)){
                sb.append(".");
                continue;
            }
            columns.add(i);
            pie.add(level+i);
            na.add(i-level);
            sb.append("Q");
            for(int j =0;j<n-1-level;j++){
                sb.append(".");
            }
            list.add(sb.toString());
            _findQueens(level+1,n,columns,pie,na,list);
            columns.remove(i);
            pie.remove(i);
            na.remove(i);
            list.remove(list.size()-1);
        }
    }
}
